package middle;

import java.util.Arrays;

public class Solution_322 {

    public int coinChange(int[] coins, int amount) {
        int[] counts = new int[amount + 1];
        Arrays.fill(counts, -1);
        counts[0] = 0;
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i >= coin && counts[i - coin] >= 0) {
                    min = Math.min(min, counts[i - coin] + 1);
                }
            }
            counts[i] = min == Integer.MAX_VALUE ? -1 : min;
        }
        return counts[amount];
    }

    public static void main(String[] args) {
        Solution_322 model = new Solution_322();
        System.out.println(model.coinChange(new int[]{186, 419, 83, 408}, 6249));
        System.out.println(model.coinChange(new int[]{1, 2, 5}, 11));
        System.out.println(model.coinChange(new int[]{2}, 3));
        System.out.println(model.coinChange(new int[]{1}, 0));
        System.out.println(model.coinChange(new int[]{1}, 1));
        System.out.println(model.coinChange(new int[]{1}, 2));
    }
}
